package org.example.基于有序数组实现;


import org.example.Priority;
import org.example.Queue;

/**
 * 基于 有 序数组实现优先级队列
 * @param <E>
 */
public class PriorityQueue2<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    public PriorityQueue2(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        insert(e);
        size++;
        return true;
    }

    private void insert(E e) {
        int index = size - 1;
        while (index >= 0 && array[index].priority() < array[index - 1].priority()) {
            array[index + 1] =array[index];
            index--;
        }
        array[index + 1] = e;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E e = (E) array[size-1];
        array[--size] = null; // help gc
        return e;
    }


    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
